package leetcode.erfen;

import java.util.Arrays;

public class A2563 {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);
        int length=nums.length;
        int res=0;
        //有序
        //1 2 5 7 9
        //11   11
        //对于一个数n，二分查找x，使得 min<=x+n<=max,大于等于min的最左位置，小于等于max的最右位置
        //x>=min-n
        //x<=max-n
        for(int i=0;i<length;i++){
            int n=nums[i];
             int left=SL(0,i-1,lower-n,nums);
             int right=SR(0,i-1,upper-n+1,nums);
             res+=right-left;
        }
        return res;
    }
    //查找左边界 SearchLeft 简写SL
    int SL(int l, int r,int tar,int[] nums)
    {
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid]>=tar) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    //查找右边界 SearchRight 简写SR
    int SR(int l, int r,int tar,int[] nums)
    {
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid]<=tar) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}
